package com.springboot.java.design.data_structure;

import lombok.Data;

/**
 * @Author: TongRui乀
 * @Date: 2020/7/13 21:10
 * @description： 搜索二叉树
 * 1 父节点大于左子树小于右子树
 */
public class SearchTree {

    private static Node root;

    public static void main(String[] args) {

        insert(9);
        insert(11);
        insert(7);
        insert(8);
        insert(5);
        insert(2);
        insert(1);

        //  1 2 5 7 8 9 11

//        Result result = getByOrder(root, 5);
//
//        System.out.println(result.val);

//        printMiddleOrder(root);
//
//        System.out.println(getByMiddleOrder(root, 3).getNode().getValue());
//        System.out.println(getByMiddleOrder(root, 4).getNode().getValue());
//        System.out.println(getByMiddleOrder(root, 5).getNode().getValue());
//        System.out.println(getByMiddleOrder(root, 6).getNode().getValue());
//        System.out.println(getByMiddleOrder(root, 7).getNode().getValue());

        System.out.println(maxHeightSum(root));

    }

    public static int maxHeightSum(Node head){

        if(head == null){
            return 0;
        }

        return maxChildHeightSum(head.left) + maxChildHeightSum(head.right);
    }

    public static int maxChildHeightSum(Node head){

        if(head == null){
            return 0;
        }

        int leftHeight = maxChildHeightSum(head.left);

        int rightHeight = maxChildHeightSum(head.right);

        return Math.max(leftHeight, rightHeight) + 1;
    }


    /**
     * 插入
     *
     * @param value
     */
    public static void insert(int value) {

        if (root == null) {
            root = new Node(value);
            return;
        }

        Node p = root;

        while (p != null) {
            if (p.value > value) {
                if (p.left == null) {
                    p.left = new Node(value);
                    return;
                }
                p = p.left;
            } else {
                if (p.right == null) {
                    p.right = new Node(value);
                    return;
                }
                p = p.right;
            }
        }
    }


    public static Node find(int value) {

        if (root == null || root.value == value) {
            return root;
        }

        Node p = root;

        while (p != null) {
            if (p.getValue() > value) {
                p = p.getLeft();
            } else if (p.getValue() < value) {
                p = p.getLeft();
            } else {
                return p;
            }
        }
        return null;
    }

    /**
     * 按顺序获取指定的索引位置的节点
     * <p>
     * 联想到二叉搜索树的性质，root 大于左子树，小于右子树，如果左子树的节点数目等于 K-1，那么 root 就是结果，
     * 否则如果左子树节点数目小于 K-1，那么结果必然在右子树，否则就在左子树。因此在搜索的时候同时返回节点数目，跟 K 做对比，就能得出结果了。
     * 5
     * / \
     * 3   6
     * / \
     * 2   4
     * /
     * 1
     *
     * @return
     */
    public static Result getByOrder(Node rot, int index) {

        if (rot == null) {
            return new Result(false, 0);
        }

        Result left = getByOrder(rot.left, index);

        if (left.find) {
            return new Result(true, left.val);
        }
        // 如果成立说明 rot就是索引所在的节点
        if (index - left.val == 1) {
            return new Result(true, rot.value);
        }

        Result right = getByOrder(rot.right, index - left.val - 1);

        if (right.find) {
            return new Result(true, right.val);
        }

        return new Result(false, left.val + 1 + right.val);
    }


    /**
     * 中序遍历 查询指定位置的节点
     * <p>
     * 中序遍历  左节点 根节点 右节点
     *
     * @param rot
     * @param index
     * @return
     */
    public static Result getByMiddleOrder(Node rot, int index) {

        if (rot == null) {
            return new Result(0, null);
        }
        Result left = getByMiddleOrder(rot.left, index);

        if (left.val == index) {
            return new Result(left.val, left.node);
        }
        if (left.val + 1 == index) {
            return new Result(left.val + 1, rot);
        }
        Result right = getByMiddleOrder(rot.right, index);
        if (left.val + right.val + 1 == index) {
            return new Result(index, right.node);
        }
        return new Result(left.val + 1 + right.val, rot);
    }


    /**
     * 中序遍历
     *
     * @param rot
     */
    public static void printMiddleOrder(Node rot) {

        if (rot == null) {
            return;
        }

        if (rot.left != null) {
            printMiddleOrder(rot.left);
        }

        System.out.println(rot.value);

        if (rot.right != null) {
            printMiddleOrder(rot.right);
        }
    }


    @Data
    private static class Result {

        boolean find;

        int val;

        Node node;

        Result() {
        }

        Result(boolean find, int val) {
            this.find = find;
            this.val = val;
        }

        Result(boolean find, int val, Node node) {
            this.find = find;
            this.val = val;
            this.node = node;
        }

        Result(int val, Node node) {
            this.find = find;
            this.val = val;
            this.node = node;
        }

    }

    /**
     * 二叉树节点
     */
    @Data
    static class Node {

        Node left;

        Node right;

        int value;

        public Node(int value) {
            this.value = value;
        }

    }

}
